#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<int>> pre;
    int m,n;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int dfs(vector<vector<int>>& vec,int x,int y)
    {
        if(pre[x][y]!=-1) return pre[x][y];
        int ret=0;
        for(int i=0;i<4;i++)
        {
            int cx=x+dx[i];
            int cy=y+dy[i];
            if(cx>=0&&cx<m&&cy>=0&&cy<n&&vec[cx][cy]>vec[x][y])
                ret=max(ret,dfs(vec,cx,cy)+1);
        }
        pre[x][y]=ret;
        return ret;
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m=matrix.size();
        n=matrix[0].size();
        int ret=0;
        pre=vector<vector<int>>(m,vector<int>(n,-1));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                ret=max(ret,dfs(matrix,i,j)+1);
            }
        }
        return ret;
    }
};